package com.example.leetcode.prcatice;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test300 {

    // r[i] =  r[i-1] || r[i-1]+1;
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[]r = new int[len];
        Arrays.fill(r,1);
        for (int i =1;i<len;i++){
            for (int j = 0;j<i;j++){
                if(nums[i]>nums[j]){
                    r[i] = Math.max(r[i],r[j]+1);
                }
            }
        }
        int res = 1;
        for (int i:r) {
            res = Math.max(res,i);
        }
        return res;
    }
}


class Demo300{
    public static void main(String[] args) {
        Test300 t = new Test300();
        int []res = {1,3,6,7,9,4,10,5,6};
        System.out.println(t.lengthOfLIS(res));
    }
}